/*
 * Instance.cpp
 *
 *  Created on: May 26, 2012
 *      Author: hugo
 */

#include "Instance.h"

bool compare_edges_cost(Edge* e1,Edge* e2){ 
    if(e1->get_cost()!=e2->get_cost())
        return e1->get_cost()<e2->get_cost();
    else
        return e1->get_sum_prize()>e2->get_sum_prize();
}
bool compare (Vertex* v1,Vertex *v2) { return (v1->get_id()<v2->get_id()); }
bool compare_prize (Vertex* v1,Vertex *v2) { return (v1->get_prize()<v2->get_prize()); }

Instance::Instance(string arq_name) {
	Instance::arq_name = arq_name;
	total_prize=0;
	loadFile();
}

Instance::~Instance() {
    for (int i = 0; i < num_vertex(); i++) {
		for (int j = 0; j < num_vertex(); j++) {
			//if(matriz[i][j]!=NULL)
			    //delete matriz[i][j];
			if(path_v!=NULL)
    			free(path_v[i][j]);
		}
		if(path_v!=NULL)
    		free(path_v[i]);
        if(path_next!=NULL)
    		free(path_next[i]);
    	if(path_prize!=NULL)
    		free(path_prize[i]);
    	if(path_cost!=NULL)
    		free(path_cost[i]);
    		
		free(matriz[i]);
	}
	if(path_v!=NULL)
		free(path_v);
    if(path_next!=NULL)
		free(path_next);
	if(path_prize!=NULL)
		free(path_prize);
	if(path_cost!=NULL)
		free(path_cost);
	free(matriz);
}

Edge* Instance::get_edge(int _i,int _j){
	return Instance::matriz[_i][_j];
}

Edge* Instance::get_edge(int _i){
	return edges.at(_i);
}

int Instance::compare_edges(Edge* e1,Edge* e2){
	int e1_prize = get_vertex(e1->get_i())->get_prize()+get_vertex(e1->get_j())->get_prize();
	int e2_prize = get_vertex(e2->get_i())->get_prize()+get_vertex(e2->get_j())->get_prize();

	if(e1->get_cost()-e1_prize<e2->get_cost()-e2_prize)
		return 1;
	else if(e1->get_cost()-e1_prize>e2->get_cost()-e2_prize)
		return -1;
	return 0;
}

Vertex* Instance::get_vertex(int _i){
	return Instance::vertexs.at(_i);
}

void Instance::loadFile() {
	cout << "loading " << Instance::arq_name << endl;
	ifstream inst_file;
	inst_file.open(Instance::arq_name.c_str());
	string output;
	int mode=-1;
	int max_node=0;
	int max_edge=0;
	if (inst_file.is_open()) {
		bool has_end=false;
		while (!inst_file.eof() && !has_end) {
			inst_file >> output;
			if(output!="#"){
				if(output=="node"){
					mode = 0;
					for(int i=0;i<4;i++)
						inst_file >> output;
					continue;
				}
				if(output=="link"){
					mode = 1;
					for(int i=0;i<5;i++)
						inst_file >> output;
					continue;
				}
			}
			if(mode==0){
				int node;
				float v1,v2,prize;
				total_prize=0;
				//for(int i=0;i<500;i++){
				bool read=true;
				while(read){
				//for(int i=0;i<8;i++){
					inst_file >> node;
					inst_file >> v1;
					inst_file >> v2;
					inst_file >> prize;
					total_prize+=prize;
					Vertex *vertex = new Vertex(node-1,prize);
					Instance::vertexs.push_back(vertex);
					vertexs_prize.push_back(vertex);
					vector<int> nb;
					neighbors.push_back(nb);
					//cout << vertex->get_id() << ":" <<vertex->get_prize()<<endl;
					max_node=max(max_node,node);

					int pos =inst_file.tellg();
					string ss;
					inst_file >> ss;
					read = ss!="link";
					inst_file.seekg(pos);
				}


				total_vertex = max_node;
				sort(vertexs.begin(),vertexs.end(),compare);
				sort(vertexs_prize.begin(),vertexs_prize.end(),compare_prize);
				mode=-1;
			}

			if(mode==1){
				Instance::matriz = (Edge***) malloc(sizeof(Edge**) * max_node);
				for (int i = 0; i < max_node; i++) {
					matriz[i] = (Edge **) malloc(sizeof(Edge*) * max_node);
					for (int j = 0; j < max_node; j++) {
						matriz[i][j] = NULL;
					}
				}
				int edge,node1,node2;
				float cost;
				//for(int i=0;i<1000;i++){
				//for(int i=0;i<12;i++){
				bool read=true;
				max_edge=0;
				while(read){
					inst_file >> edge;
					inst_file >> node1;
					inst_file >> node2;
					inst_file >> cost;
//					float val = get_vertex(node1-1)->get_prize() + get_vertex(node2-1)->get_prize() - cost;

					//if(val>=0){
						matriz[node1-1][node2-1] = new Edge(max_edge++,get_vertex(node1-1),get_vertex(node2-1),cost);
						matriz[node2-1][node1-1] = matriz[node1-1][node2-1];
						//neighbors.at(node1-1).push_back(node2-1);
						//neighbors.at(node2-1).push_back(node1-1);
						//edges.push_back(matriz[node2-1][node1-1]);
					//}
					//cout << edge<<"("<< node1<<","<<node2<<")" << ":" <<get_edge(node1-1,node2-1)->get_cost()<<endl;

					int pos =inst_file.tellg();
					string ss;
					inst_file >> ss;
					read = ss!="";
					inst_file.seekg(pos);
					//max_edge=max(max_edge,edge);
				}
				has_end=true;
				total_edge = max_edge;
				mode=-1;
			}
		}
		cout << "Instance ready:"<<endl;
		cout << "\t"<<total_vertex<<" nodes"<<endl;
		cout << "\t"<<total_edge<<" edges"<<endl;
		cout << "\t"<<get_total_prize()<<" prize"<<endl;
	}else{
		cout << "Error:: File not found" << endl;
	}
	inst_file.close();
}
long Instance::num_vertex(){
	return total_vertex;
}
long Instance::num_edge(){
	return total_edge;
}
float Instance::get_total_prize(){
	return total_prize;
}
float Instance::avg_degree(int id){
	float total=0;
	float sum_cost=0;
	for(int i=0;i<num_vertex();i++){
		Edge *e = get_edge(id,i);
		if(e!=NULL){
			sum_cost+=e->get_cost();
			total++;
		}
	}
	cout << "Node "<< (id+1) << "=" << sum_cost << "/" << total<<endl;
	return total>0?sum_cost/total:0;
}
float Instance::avg_degree(Vertex* v){
	return avg_degree(v->get_id());
}

vector<int> Instance::neighborhood(int v_id){
	return neighbors.at(v_id);
}

void Instance::init_short_path(){
    path_cost = (float**) malloc(sizeof(float*) * num_vertex());
    path_prize = (float**) malloc(sizeof(float*) * num_vertex());
    path_next = (int**) malloc(sizeof(int*) * num_vertex());
	for (int i = 0; i < num_vertex(); i++) {
		path_cost[i] = (float*) malloc(sizeof(float) * num_vertex());
		path_prize[i] = (float*) malloc(sizeof(float) * num_vertex());
		path_next[i] = (int*) malloc(sizeof(int) * num_vertex());
		for (int j = 0; j < num_vertex(); j++) {
    		path_next[i][j]=-1;
		    if(i==j){
		        path_cost[i][j]=0;
		        path_prize[i][j]=get_vertex(i)->get_prize();
		        path_next[i][j]=i;
		    }else{
		        Edge *e = get_edge(i,j);
		        if(e!=NULL){
        	        path_next[i][j]=i;
        			path_cost[i][j]=e->get_cost();
        			path_prize[i][j]=get_vertex(i)->get_prize()+get_vertex(j)->get_prize();
        		}else{
        		    path_cost[i][j]=9000.00;
        		    path_prize[i][j]=0;
        		}
    		}
		}
	}
}

void Instance::init_short_path_prize(){
    path_v = (int***) malloc(sizeof(int*) * num_vertex());
    for(int k=0;k<num_vertex();k++){
        path_v[k]=(int**) malloc(sizeof(int*) * num_vertex());
        for(int i=0;i<num_vertex();i++){
            path_v[k][i]=(int*) malloc(sizeof(int) * num_vertex());
            for(int j=0;j<num_vertex();j++)
                path_v[k][i][j]=0;
        }
    }
    
    path_cost = (float**) malloc(sizeof(float*) * num_vertex());
    path_prize = (float**) malloc(sizeof(float*) * num_vertex());
    path_next = (int**) malloc(sizeof(int*) * num_vertex());
	for (int i = 0; i < num_vertex(); i++) {
		path_cost[i] = (float*) malloc(sizeof(float) * num_vertex());
		path_prize[i] = (float*) malloc(sizeof(float) * num_vertex());
		path_next[i] = (int*) malloc(sizeof(int) * num_vertex());
		for (int j = 0; j < num_vertex(); j++) {
    		path_next[i][j]=-1;
		    if(i==j){
		        path_cost[i][j]=0;
		        path_prize[i][j]=get_vertex(i)->get_prize();
		        path_next[i][j]=i;
		    }else{
		        Edge *e = get_edge(i,j);
		        if(e!=NULL){
        	        path_next[i][j]=i;
        			path_prize[i][j]=get_vertex(i)->get_prize()+get_vertex(j)->get_prize();
        			path_cost[i][j]=e->get_cost();
        		}else{
        		    path_cost[i][j]=9000.00;
        		    path_prize[i][j]=get_vertex(i)->get_prize()+get_vertex(j)->get_prize();
        		}
    		}
		}
	}
}


void Instance::calculate_short_path_prize(){
    init_short_path_prize();
	for(int k=0;k<num_vertex();k++){
	    cout << k <<":"<<endl;
    	for(int i=0;i<num_vertex();i++){
        	for(int j=0;j<num_vertex();j++){
        	    if(k==i || k==j || i==j) continue;
        	    //cout << (k+1)<< " : " << (i+1) <<" , "<<(j+1)<<endl;
        	    //if(has_vertex_at_path(i,k,j) || has_vertex_at_path(k,j,i))continue;
        	    if(path_v[i][k][j] || path_v[k][j][i])continue;
        	    float tmp_prize = path_prize[i][k]+path_prize[k][j] - get_vertex(k)->get_prize();
        	    if(path_cost[i][j]+total_prize-path_prize[i][j] > path_cost[i][k]+path_cost[k][j]+total_prize-tmp_prize){
        	        path_cost[i][j] = path_cost[i][k]+path_cost[k][j];
        	        path_prize[i][j] = tmp_prize;
        	        path_next[i][j] = k;
        	        for(int l=0;l<num_vertex();l++)
        	            path_v[i][j][l]=path_v[i][k][l] || path_v[k][j][l];
        	        path_v[i][j][k]=1;
        	    }
        	}
	    }
	}
	int best=-1;
	float val;
	for(int k=0;k<num_vertex();++k){
	    int count=0;
	    for(int i=0;i<num_vertex();++i){
	        for(int j=0;j<num_vertex();++j){
	            count+=path_v[i][j][k];
	        }
	    }
	    if(best==-1 || val<count){
	        val = count;
	        best = k;
	    }
	    cout<< k<<":"<< count << endl;
    }
    golden_node = best;
/*	for(int i=0;i<num_vertex();++i){
	    for(int j=i;j<num_vertex();++j){
	        cout << "("<< (i+1) << "," << (j+1)<< ") = "<<path_cost[i][j]<< " | "<<path_prize[i][j] <<":";
	        print_path(i,j);
	        cout << endl;
	    }
	}*/
}

void Instance::calculate_short_path_cost(){
    init_short_path();
	for(int k=0;k<num_vertex();k++){
    	for(int i=0;i<num_vertex();i++){
        	for(int j=0;j<num_vertex();j++){
        	    if(path_cost[i][j]>path_cost[i][k]+path_cost[k][j]){
        	        path_cost[i][j] = path_cost[i][k]+path_cost[k][j];
        	        path_prize[i][j] = path_prize[i][k]+path_prize[k][j] - get_vertex(k)->get_prize();
        	    }
        	}
	    }
	}
	/*for(int i=0;i<num_vertex();++i){
	    for(int j=i;j<num_vertex();++j){
	        cout << "("<< (i+1) << "," << (j+1)<< ") = "<<path_cost[i][j]<< " | "<<path_prize[i][j]<<endl;
	    }
	}*/
}

int Instance::short_path_test(){
    int removed=0;
    for(int i=0;i<num_vertex();i++){
        for(int j=i+1;j<num_vertex();j++){
            Edge *e = matriz[i][j];
            if(e!=NULL && e->get_cost()>path_cost[e->get_i()][e->get_j()]){
                removed++;
                matriz[e->get_i()][e->get_j()]=NULL;
                matriz[e->get_j()][e->get_i()]=NULL;
                //cout << e->get_id()+1<<endl;
            }
        }
    }
    //cout << "Removidas "<< removed<<endl;
    return removed;
}
void Instance::short_path_test_prize(){
    int removed=0;
    for(int i=0;i<num_vertex();i++){
        for(int j=i+1;j<num_vertex();j++){
            Edge *e = matriz[i][j];
            if(e!=NULL){
                float prize = get_vertex(e->get_i())->get_prize()+get_vertex(e->get_j())->get_prize();
                if(e->get_cost()+(total_prize-prize)>path_cost[e->get_i()][e->get_j()]+(total_prize-path_prize[e->get_i()][e->get_j()])){
                    removed++;
                    matriz[e->get_i()][e->get_j()]=NULL;
                    matriz[e->get_j()][e->get_i()]=NULL;
                    //cout << e->get_id()+1<<endl;
                }
            }
        }
    }
    //cout << "Removidas Prize "<< removed<<endl;
}
int Instance::short_path_cost_test(){
    calculate_short_path_cost();
    return short_path_test();
}

void Instance::short_path_prize_test(){
    calculate_short_path_prize();
    short_path_test_prize();
}

bool Instance::has_vertex_at_path(int i,int j, int k){
    return path_v[i][j][k];
}

int Instance::card_one_test(){
	int degree_one=0;
	for(int i=0;i<num_vertex();i++){
		int degree=0;
		int m=-1;
		for(int j=i+1;j<num_vertex();++j){
			if(get_edge(i,j)!=NULL){
				degree++;
				m=j;
			}
		}
		if(degree==1 && get_edge(i,m)->get_cost()>get_vertex(i)->get_prize()){
			degree_one++;
			matriz[i][m]=NULL;
			matriz[m][i]=NULL;
		}
	}
	//cout << "Qnt degree one: "<<degree_one<<endl;
	return degree_one;
}

int Instance::card_two_test(){
	int degree_two=0;
	for(int i=0;i<num_vertex();i++){
		int degree=0;
		int m,n;
		m=n=-1;
		for(int j=i+1;j<num_vertex();++j){
			if(get_edge(i,j)!=NULL){
				degree++;
				if(m==-1)
					m=j;
				else
					n=j;
			}
		}
		if(degree==2 && get_vertex(i)->get_prize()==0){
			degree_two ++;
			float new_cost = get_edge(i,m)->get_cost()+get_edge(i,n)->get_cost();
			if(get_edge(n,m)==NULL){
				matriz[n][m] = new Edge(-1,get_vertex(n),get_vertex(m),new_cost);
				matriz[m][n] = matriz[n][m];
			}else{
				get_edge(n,m)->set_cost(min(new_cost,get_edge(n,m)->get_cost()));
			}
			matriz[i][m]=NULL;
			matriz[m][i]=NULL;
			matriz[i][n]=NULL;
			matriz[n][i]=NULL;
		}
	}
	cout << "Qnt degree two: "<<degree_two<<endl;
	return degree_two;
}

void Instance::pre_test(){
    int qnt;
    int total=0;
    do{
        qnt=0;
        qnt+=short_path_cost_test();
        //qnt+=card_two_test();
        //qnt+=card_one_test();
        total+=qnt;
    }while(qnt>0);
    cout << "Removidas "<<total<<endl;
	set_values();
}

void Instance::set_values(){
	total_edge=0;
	for(int i=0;i<num_vertex();i++){
		for(int j=i+1;j<num_vertex();j++){
			if(matriz[i][j]!=NULL){
				matriz[i][j]->set_id(total_edge++);
				neighbors.at(i).push_back(j);
				neighbors.at(j).push_back(i);
				edges.push_back(matriz[i][j]);
				edges_sorted.push_back(matriz[i][j]);
			}
		}
	}
	sort(edges_sorted.begin(),edges_sorted.end(),compare_edges_cost);
}

float Instance::get_path_cost(int i,int j){
    return path_cost[i][j];
}
float Instance::get_path_prize(int i,int j){
    return path_prize[i][j];
}

void Instance::print_path(int i,int j){
    if(path_next[i][j]==-1){
        cout << "no path" << endl;
    }else if(path_next[i][j]==i){
        cout << " ";
    }else{
        print_path(i,path_next[i][j]);
        cout <<" "<< (path_next[i][j]+1)<< " ";
        print_path(path_next[i][j],j);
    }
}

Vertex* Instance::get_vertex_sorted_by_prize(int i){
    return vertexs_prize[i];
}

Edge* Instance::get_edge_sorted_by_cost(int i){
    return edges_sorted[i];
}

int Instance::get_golden_node(){
    return golden_node;
}
